/**
 * Setvor project
 */
package setvor.lang.machine;

import java.util.*;
import setvor.lang.*;

/**
 * This class implements some basic methods in automata.
 * @author julatec
 */
public abstract class AbstractAutomaton<Q extends State<Q>, S> implements Automaton<Q, S> {
	
	/**
	 * This is a empty set.
	 */
	protected transient final Set<Q> emptySet;
	
	/**
	 * Basic constructor
	 */
	protected AbstractAutomaton(){
		this.emptySet = new LinkedHashSet<Q>(); 
	}
	
	public Set<Q> analize(StringOf<S> string){
		Set<Q> currentStates = getInitialState();
		if(isDeterministic())
			for(S symbol : string){
				if(currentStates == null || currentStates.isEmpty())
					break;
				currentStates = nextOnSymbol(currentStates, symbol);
			}
		else
			for(S symbol : string){
				if(currentStates == null || currentStates.isEmpty())
					break;
				Set<Q> onEmptyStepBefore = nextOnEmptyString(currentStates);
				onEmptyStepBefore.addAll(currentStates);
				Set<Q> onStep = nextOnSymbol(onEmptyStepBefore, symbol);
				currentStates = nextOnEmptyString(onStep);
				currentStates.addAll(currentStates);
			}		
		return currentStates;
	}
	
	/**
	 * 
	 * @return
	 */
	protected final Set<Q> getEmptySet(){
		return emptySet;
	}
	
	/**
	 * This class represent 
	 * @author julatec
	 *
	 * @param <T>
	 */
	protected static class OneElementSet<T> extends LinkedHashSet<T>{
				
		private static final long serialVersionUID = 1L;

		/**
		 * This constructor takes one element and create new set.
		 * @param element
		 */
		public OneElementSet(T element){
			super();
			this.add(element);
		}
		
	}
	
	protected Set<Q> nextOnSymbol(Set<Q> currentStates, S symbol){
		Set<Q> result = new LinkedHashSet<Q>();
		for(Q currentState : currentStates)
			for(Q nextState : this.transition(currentState, symbol))
				if(nextState != null)
					result.add(nextState);
		return result;
	}
	
	protected Set<Q> nextOnEmptyString(Set<Q> currentStates){
		if(acceptEmptyString())
			return this.emptySet;
		Set<Q> result = new LinkedHashSet<Q>();
		Set<Q> newStates = new LinkedHashSet<Q>();
		while(true){
			for(Q currentState : currentStates){
				if(currentState == null)
					continue;
				Set<Q> next = this.emptyTransition(currentState);
				if(next == null || next.isEmpty())
					continue;
				for(Q nextState : currentStates){
					if(nextState == null ||
							currentStates.contains(nextState) || 
							result.contains(nextState))
						continue;
					newStates.add(nextState);
				}
			}			
			if(newStates.isEmpty())
				break;
			result.addAll(newStates);
			currentStates = newStates;
		}
		return result;
	}
	
	protected Set<Q> finalStates = null;
		
	public synchronized Set<Q> getFinalStates(){
		if(isFinite() && finalStates == null){
			finalStates = new java.util.LinkedHashSet<Q>();
			for(Q state : this.getStates())
				if(state.isFinal())
					finalStates.add(state);
		}
		return finalStates;
	}
	
	public boolean accept(StringOf<S> string){		
		for(Q state : analize(string))
			if(state != null && state.isFinal())
				return true;		
		return false;
	}

}
